package day0311

import "fmt"

func longestValidParentheses(s string) int {
	maxVal := 0
	n := len(s)
	dp := make([]int, n)
	for i := 1; i < n; i++ {
		if s[i] == ')' {
			if s[i-1] == '(' {
				if i > 2 {
					dp[i] = dp[i-2] + 2
				} else {
					dp[i] = 2
				}
			} else if i-dp[i-1] >= 1 && s[i-dp[i-1]-1] == '(' {
				if i-dp[i-1] >= 2 {
					dp[i] = dp[i-dp[i-1]-2] + 2 + dp[i-1]
				} else {
					dp[i] = 2 + dp[i-1]
				}
			}
		}
		maxVal = max(dp[i], maxVal)
	}
	fmt.Println(dp)
	return maxVal
}

func max(a, b int) int {
	if a >= b {
		return a
	}
	return b
}
